{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Elements in Array After Removing and Replacing Elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: elementInNums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查询删除和添加元素后的数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<strong>下标从 0 开始</strong>&nbsp;的数组&nbsp;<code>nums</code>。一开始，在第 <code>0</code> 分钟，数组没有变化。此后每过一分钟，数组的 <strong>最左边</strong> 的元素将被移除，直到数组为空。然后，每过一分钟，数组的 <strong>尾部</strong> 将添加一个元素，添加的顺序和删除的顺序相同，直到数组被复原。此后上述操作无限循环进行。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>举个例子，如果 <code>nums = [0, 1, 2]</code>，那么数组将按如下流程变化：<code>[0,1,2] → [1,2] → [2] → [] → [0] → [0,1] → [0,1,2] → [1,2] → [2] → [] → [0] → [0,1] → [0,1,2] → ...</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>然后给你一个长度为 <code>n</code> 的二维数组 <code>queries</code>，其中 <code>queries[j] = [time<sub>j</sub>, index<sub>j</sub>]</code>，表示第 <code>j</code> 个查询。第 <code>j</code> 个查询的答案定义如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果在时刻&nbsp;<code>time<sub>j</sub></code>，<code>index<sub>j</sub> &lt; nums.length</code>，那么答案是此时的 <code>nums[index<sub>j</sub>]</code>；</li>\n",
    "\t<li>如果在时刻&nbsp;<code>time<sub>j</sub></code>，<code>index<sub>j</sub> &gt;= nums.length</code>，那么答案是 <code>-1</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请返回一个长度为 <code>n</code> 的整数数组 <code>ans</code>，其中 <code>ans[j]</code> 为第 <code>j</code> 个查询的答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> nums = [0,1,2], queries = [[0,2],[2,0],[3,2],[5,0]]\n",
    "<strong>输出:</strong> [2,2,-1,0]\n",
    "<strong>解释:</strong>\n",
    "第 0 分钟: [0,1,2] - 数组和 nums 相同。\n",
    "第 1 分钟: [1,2]   - 最左侧元素 0 被移除。\n",
    "第 2 分钟: [2]     - 最左侧元素 1 被移除。\n",
    "第 3 分钟: []      - 最左侧元素 0 被移除。\n",
    "第 4 分钟: [0]     - 0 被添加到数组尾部。\n",
    "第 5 分钟: [0,1]   - 1 被添加到数组尾部。\n",
    "\n",
    "在第 0 分钟, nums[2] 是 2。\n",
    "在第 2 分钟, nums[0] 是 2。\n",
    "在第 3 分钟, nums[2] 不存在。\n",
    "在第 5 分钟, nums[0] 是 0。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> nums = [2], queries = [[0,0],[1,0],[2,0],[3,0]]\n",
    "<strong>输出:</strong> [2,-1,2,-1]\n",
    "第 0 分钟: [2] - 数组和 nums 相同。\n",
    "第 1 分钟: []  - 最左侧元素 2 被移除。\n",
    "第 2 分钟: [2] - 2 被添加到数组尾部。\n",
    "第 3 分钟: []  - 最左侧元素 2 被移除。\n",
    "\n",
    "在第 0 分钟, nums[0] 是 2。\n",
    "在第 1 分钟, nums[0] 不存在。\n",
    "在第 2 分钟, nums[0] 是 2。\n",
    "在第 3 分钟, nums[0] 不存在。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 100</code></li>\n",
    "\t<li><code>n == queries.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>queries[j].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= time<sub>j</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= index<sub>j</sub> &lt; nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [elements-in-array-after-removing-and-replacing-elements](https://leetcode.cn/problems/elements-in-array-after-removing-and-replacing-elements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [elements-in-array-after-removing-and-replacing-elements](https://leetcode.cn/problems/elements-in-array-after-removing-and-replacing-elements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,2]\\n[[0,2],[2,0],[3,2],[5,0]]', '[2]\\n[[0,0],[1,0],[2,0],[3,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 切片模拟\n",
    "    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        states = []\n",
    "        for i in range(n):\n",
    "            states.append(nums[i:])\n",
    "        for i in range(n):\n",
    "            states.append(nums[:i])\n",
    "\n",
    "        res = []\n",
    "        for cycle, index in queries:\n",
    "            cycle %= len(states)\n",
    "            cand = states[cycle][index : index + 1]\n",
    "            res.append(cand[0] if cand else -1)\n",
    "\n",
    "        return res\n",
    "        \n",
    "    # 找规律\n",
    "    def elementInNums2(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        每过一分钟，数组的 最左边 的元素将被移除，直到数组为空。\n",
    "        然后，每过一分钟，数组的 尾部 将添加一个元素\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        res = [-1] * len(queries)\n",
    "        for i, (time, pos) in enumerate(queries):\n",
    "            time %= 2 * n\n",
    "            if time < n and pos < n - time:\n",
    "                # 数组长度为 n-time ，查询 time + pos\n",
    "                res[i] = nums[time + pos]\n",
    "            elif time > n and pos < time - n:\n",
    "                # 数组长度为 time-n，查询 pos\n",
    "                res[i] = nums[pos]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 找规律\n",
    "    def elementInNums1(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        每过一分钟，数组的 最左边 的元素将被移除，直到数组为空。\n",
    "        然后，每过一分钟，数组的 尾部 将添加一个元素\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        res = [-1] * len(queries)\n",
    "        for i, (time, pos) in enumerate(queries):\n",
    "            time %= 2 * n\n",
    "            if time < n and pos < n - time:\n",
    "                # 数组长度为 n-time ，查询 time + pos\n",
    "                res[i] = nums[time + pos]\n",
    "            elif time > n and pos < time - n:\n",
    "                # 数组长度为 time-n，查询 pos\n",
    "                res[i] = nums[pos]\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "    # 切片模拟\n",
    "    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        states = []\n",
    "        for i in range(n):\n",
    "            states.append(nums[i:])\n",
    "        for i in range(n):\n",
    "            states.append(nums[:i])\n",
    "\n",
    "        res = []\n",
    "        for cycle, index in queries:\n",
    "            cycle %= len(states)\n",
    "            cand = states[cycle][index : index + 1]\n",
    "            res.append(cand[0] if cand else -1)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = [-1] * len(queries)\n",
    "        for i, (t, idx) in enumerate(queries):\n",
    "            t %= 2 * n\n",
    "            if t < n and idx < n - t:\n",
    "                ans[i] = nums[t + idx]\n",
    "            elif t > n and idx < t - n:\n",
    "                ans[i] = nums[idx]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        t=[0]*n*2\n",
    "        t[0]=n \n",
    "        for i in range(1,n*2):\n",
    "            if i<=n:\n",
    "                t[i]=t[i-1]-1\n",
    "            else:\n",
    "                t[i]=t[i-1]+1\n",
    "        res=[]\n",
    "        for time,q in queries:\n",
    "            time%=(n*2)\n",
    "            if q<t[time]:\n",
    "                if time<n:\n",
    "                    res.append(nums[time+q])\n",
    "                else:\n",
    "                    res.append(nums[q])\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        for t, p in queries:\n",
    "            t %= (n * 2)\n",
    "            if t <= n:\n",
    "                cur = nums[t:]\n",
    "            else:\n",
    "                cur = nums[:t - n]\n",
    "            if p < len(cur):\n",
    "                ans.append(cur[p])\n",
    "            else:\n",
    "                ans.append(-1)\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * len(queries)\n",
    "        for i, (t, idx) in enumerate(queries):\n",
    "            t %= 2 * n\n",
    "            if t < n and idx < n - t:\n",
    "                ans[i] = nums[t + idx]\n",
    "            elif t > n and idx < t - n:\n",
    "                ans[i] = nums[idx]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = [-1] * len(queries)\n",
    "        for i, (t, idx) in enumerate(queries):\n",
    "            t %= 2 * n\n",
    "            if t < n and idx < n - t:\n",
    "                ans[i] = nums[t + idx]\n",
    "            elif t > n and idx < t - n:\n",
    "                ans[i] = nums[idx]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        T = 2 * n \n",
    "        ans = []\n",
    "\n",
    "        def f(i, j):\n",
    "            i %= T\n",
    "            if i == n:\n",
    "                return -1\n",
    "            elif i > n:\n",
    "                ln = i - n \n",
    "                if j < ln:\n",
    "                    return nums[j]\n",
    "                return -1\n",
    "            else:\n",
    "                ln = n - i \n",
    "                if j < ln:\n",
    "                    return nums[i + j]\n",
    "                return -1\n",
    "        \n",
    "        for x, y in queries:\n",
    "            ans.append(f(x, y))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 数学\n",
    "    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * len(queries)\n",
    "        for i, (t, idx) in enumerate(queries):\n",
    "            t %= 2 * n\n",
    "            if t < n and idx < n - t:\n",
    "                ans[i] = nums[t + idx]\n",
    "            elif t > n and idx < t - n:\n",
    "                ans[i] = nums[idx]\n",
    "                \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * len(queries)\n",
    "        for i, (t, idx) in enumerate(queries):\n",
    "            t %= 2 * n\n",
    "            if t < n and idx < n - t:\n",
    "                ans[i] = nums[t + idx]\n",
    "            elif t > n and idx < t - n:\n",
    "                ans[i] = nums[idx]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 找规律\n",
    "    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        每过一分钟，数组的 最左边 的元素将被移除，直到数组为空。\n",
    "        然后，每过一分钟，数组的 尾部 将添加一个元素\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        res = [-1] * len(queries)\n",
    "        for i, (time, pos) in enumerate(queries):\n",
    "            time %= 2 * n\n",
    "            if time < n and pos < n - time:\n",
    "                # 数组长度为 n-time ，查询 time + pos\n",
    "                res[i] = nums[time + pos]\n",
    "            elif time > n and pos < time - n:\n",
    "                # 数组长度为 time-n，查询 pos\n",
    "                res[i] = nums[pos]\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        for time, index in queries:\n",
    "            i = time % (n * 2)\n",
    "            if i >= n:\n",
    "                i = i % n - 1\n",
    "                if index <= i:\n",
    "                    ans.append(nums[index])\n",
    "                else:\n",
    "                    ans.append(-1)\n",
    "            else:\n",
    "                if index <= n - i - 1:\n",
    "                    ans.append(nums[i + index])\n",
    "                else:\n",
    "                    ans.append(-1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = [-1] * len(queries)\n",
    "        for i, (t, idx) in enumerate(queries):\n",
    "            t %= 2 * n\n",
    "            if t < n and idx < n - t:\n",
    "                ans[i] = nums[t + idx]\n",
    "            elif t > n and idx < t - n:\n",
    "                ans[i] = nums[idx]\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
